﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
#include <ctype.h>
#include <string.h>
//2024.01.10比特假期作业代码题——day08

//字符个数统计——字符串、哈希——简单
//描述
//编写一个函数，计算字符串中含有的不同字符的个数。字符在 ASCII 码范围内(0~127 ，包括 0 和 127)，换行表示结束符，不算在字符里。不在范围内的不作统计。多个相同的字符只计算一次
//例如，对于字符串 abaca 而言，有 a、b、c 三种不同的字符，因此输出 3 。
//数据范围：
//1≤n≤500
//输入描述：
//输入一行没有空格的字符串。
//输出描述：
//输出 输入字符串 中范围在(0~127，包括0和127)字符的种数。
//示例1
//输入：
//abc
//输出：
//3
//示例2
//输入：
//aaa
//输出：
//1
int cmp1(const void* p1, const void* p2) {
	return *(char*)p1 - *(char*)p2;
}
void test1() {
	int n = 0;
	while (scanf("%d", &n) == 1) {
		char* ch = (char*)calloc(n + 1, sizeof(char));
		assert(ch);
		scanf("%s", ch);
		qsort(ch, strlen(ch), sizeof(char), cmp1);
		int count = 0;
		for (int i = 0; i < strlen(ch) - 1; i++) {
			if (ch[i] == ch[i + 1])
				continue;
			else {
				count++;
			}
		}
		printf("%d\n", count);
		free(ch);
	}
}
void test1_2() {
	int n = 0;
	while (scanf("%d", &n) == 1) {
		char* ch = (char*)calloc(n + 1, sizeof(char));
		assert(ch);
		scanf("%s", ch);
		int count = 0;
		for (int i = 0; i < strlen(ch) - 1; i++) {
			if (ch[i] != ch[i + 1])
				count++;
		}
		printf("%d\n", count);
		free(ch);
	}
}
void test1_3() {
	char ch[501] = { 0 };
	while (scanf("%s", ch) == 1) {
		int count = 0;
		qsort(ch, strlen(ch), sizeof(char), cmp1);
		for (size_t i = 0; i < strlen(ch); i++) {
			if ((ch[i] != ch[i + 1]) && (ch[i] >= 0 && ch[i] <= 127))
				count++;
		}
		printf("%d\n", count);
	}
}

// 多数元素——数组、哈希表、分治、计数、排序——简单
//给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n / 2 ⌋ 的元素。
//你可以假设数组是非空的，并且给定的数组总是存在多数元素。
//示例 1：
//输入：nums = [3, 2, 3]
//输出：3
//示例 2：
//输入：nums = [2, 2, 1, 1, 1, 2, 2]
//输出：2
//提示：
//n == nums.length
//1 <= n <= 5 * 10^4
//- 10^9 <= nums[i] <= 10^9
//进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
int cmp_int(const void* p1, const void* p2) {
	return *(int*)p1 - *(int*)p2;
}
int majorityElement(int* nums, int numsSize) {
	qsort(nums, numsSize, sizeof(int), cmp_int);
	int count = 1, ans = 0;
	for (int i = 0; i < numsSize; i++) {
		for (int j = i; j < numsSize - 1; j++) {
			if (nums[j] != nums[j + 1]) {
				i = j;
				break;
			}
			else {
				count++;
			}
		}
		if (count > numsSize / 2) {
			ans = nums[i];
			break;
		}
	}
	return ans;
}
void test2() {
	int n = 0;
	while (scanf("%d", &n) == 1) {
		int* p = (int*)calloc(n, sizeof(int));
		assert(p);
		for (int i = 0; i < n; i++)
			scanf("%d", &p[i]);
		int ret = majorityElement(p, n);
		printf("%d\n", ret);
		free(p);
	}
}

int main() {
	return 0;
}